package classic

import kotlin.math.max
import kotlin.math.min

/**
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。(只能交易一次) 设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 *
 * 示例1：
 * 输入：[7,1,5,3,6,4]
 * 输出：5
 * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
fun maxProfit(prices: IntArray): Int {
    var res = 0
    for (i in 1 until prices.size) {
        val value = prices[i] - prices[i - 1]
        if (value > 0) res += value
    }
    return res
}

/**
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。(能交易多次) 设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 *
 * 示例1：
 * 输入：[7,1,5,3,6,4，0]
 * // 假设我当前第一天买入股票的最小支出是 -7，最大收益是 0
 * // 假设我当前第二天买入股票的最小支出是 -1，卖出收益是 -6
 * // 假设我当前第三天买入股票的最小支出是 -1，卖出收益是 4
 * // 假设我当前第四天买入股票的最小支出是 -1，卖出收益是 2
 * // 假设我当前第五天买入股票的最小支出是 -1，卖出收益是 5
 * // 假设我当前第六天买入股票的最小支出是 -1，卖出收益是 5
 * // 假设我当前第六天买入股票的最小支出是 0，卖出收益是 -1
 *
 * 输出：5
 * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
fun maxProfit1(prices: IntArray): Int {
    // 创建 prices.size * 2 数组
    val arr = Array(prices.size) { IntArray(2) }
    //array[0] 表示买这股票的最大收益， array[1] 表示买出股票的最大收益
    arr[0][0] = -prices[0]
    arr[0][1] = 0
    for (index in 1 until prices.size) {
        val temp = prices[index]
        arr[index][0] = max(-temp, arr[index - 1][0])
        arr[index][1] = max(arr[index - 1][1], temp + arr[index][0])
    }
    return arr[arr.size - 1][1]
}

fun maxProfit11(prices: IntArray): Int {
    // 创建 prices.size * 2 数组
    var minOut = prices[0]
    var maxIn = 0
    for (index in 1 until prices.size) {
        minOut = min(minOut, prices[index])
        maxIn = max(maxIn, prices[index] - minOut)
    }
    return maxIn
}

fun main() {
    val arrays = intArrayOf(7, 1, 5, 3, 6, 4, -1, 2)
    println(maxProfit11(arrays))
}
